Counter (CTR) mode takes a different approach to most other modes of operation. It does not even use the block cipher's encryption function on the message itself!

The encryption process begins by dividing the message into blocks with length . Then, an initialisation vector (IV) of length is randomly generated. However, instead of passing the -th block to , CTR mode takes the IV and appends to it a counter encoded as a binary string of length and inputs this into . The -th message block is then XOR-ed with the output to produce the -th ciphertext block:

The final ciphertext is obtained by concatenating all ciphertext blocks and prepending them with the initialisation vector, which is necessary for decryption just as with CBC mode.

This process essentially turns a block cipher into a stream cipher where the IV and the counter are used to generate a keystream which is then XOR-ed with the message.

The decryption procedure is almost equivalent - the IV is extracted from the ciphertext and the rest of it is divided into ciphertext blocks . The -th ciphertext block is XOR-ed with the output of, notice, after passing it the concatenation of the IV and encoded as a binary string of length .

That's right - the decryption function of the block cipher is not even used! This means that the encryption function does not need to even be invertible, i.e. it does not need to be a pseudorandom permutation (PRP), but can simply be a pseudorandom function (PRF). This is only one major advantage of CTR mode. Another one is the fact that both encryption and decryption are parallelisable, which makes them excellent candidates for optimisation. These two factors, combined with the security provided by this mode, are the reason for CTR's extensive use.

So long as the initialisation vector is chosen uniformly at random and the block cipher used is secure, i.e. it uses a pseudorandom function (or permutation) for its function, CTR mode will be CPA-secure.

First suppose, towards contradiction, that there is an efficient adversary Eve that after querying $\textit{Enc}_k$ with $q$ messages $m_1, m_2, ..., m_q$ and obtaining their ciphertexts $c_1, c_2, ..., c_q$, can distinguish with probability $\frac{1}{2} + \textit{nonnegl}(n)$ if a ciphertext $c$ is the encryption of $m_a$ or $m_b$, for some messages $m_a$ and $m_b$, which are also allowed to be one of the previously queried messages. 

Consider the case where the messages $m_a$ and $m_b$ are only a single block long. If instead of the PRF $\textit{Enc}_k$, the CTR encryption used a truly random function $R$, then Eve would lack any information and so she would only be able guess at best with probability $\frac{1}{2}$ whether a ciphertext $c$ belongs to $m_a$ or $m_b$. This, however, is a contradiction because she would be able to distinguish with non-negligible probability the output of a PRF from the output of a truly random function. Therefore, no such adversary can exist.

This reasoning assumes that the IV is never reused, but since the IV is supposed to be chosen uniformly at random, this *can* happen. So we need to show that this happens with only negligible probability.

Indeed, the adversary Eve makes $q$ queries which means $q$ messages with $q$ IV's. Each IV is chosen uniformly from $\{0,1\}^{\frac{3}{4}l_b}$, so the probability that an IV is repeated is $\frac{q^2}{2^{\frac{3}{4}l_b + 1}}$ which is negligible, since Eve must be efficient and therefore $q$ needs to be polynomial.
Copy